﻿/************************************************************************

   Extended Silverlight Toolkit

   Copyright (C) 2010-2012 Xceed Software Inc.

   This program is provided to you under the terms of the Microsoft Public
   License (Ms-PL) as published at http://extendedsilverlight.codeplex.com/license

   Please purchase a commercial version of this toolkit if you are using
   it in a commercial product. The commercial versions support the project,
   and also include more features for each control, priority support,
   source code, updates, removed watermark, and a proprietary license.

   Visit http://xceed.com and follow @datagrid on Twitter.

  **********************************************************************/

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace Xceed.Silverlight.Data
{
  public sealed class DynamicBufferConfiguration : BufferConfiguration
  {
    #region Static Fields

    private const int HistoryLength = 50;

    private const int MinimumBufferCapacity = 10;
    private const int MaximumBufferCapacity = 5000;

    private const int MinimumActivePreFetchSize = 5;
    private const int MaximumActivePreFetchSize = 1000;

    private const int MinimumPassivePreFetchSize = 0;
    private const int MaximumPassivePreFetchSize = 250;

    private const double ActivePreFetchSizeBoostRatio = 1.25d;

    private const double ShrinkThresholdRatio = 0.2d;
    private const double ShrinkRatio = 0.2d;
    private const int ShrinkCountToReleaseItems = 20;

    private static readonly TimeSpan SpareTime = TimeSpan.FromSeconds( 5d );

    #endregion

    #region Constructor

    public DynamicBufferConfiguration()
    {
    }

    public DynamicBufferConfiguration(
      int minimumBufferCapacity,
      int maximumBufferCapacity )
      : this()
    {
      m_minimumBufferCapacity = minimumBufferCapacity;
      m_maximumBufferCapacity = maximumBufferCapacity;
    }

    public DynamicBufferConfiguration(
      int minimumBufferCapacity,
      int maximumBufferCapacity,
      int minimumActivePreFetchSize,
      int maximumActivePreFetchSize )
      : this( minimumBufferCapacity, maximumBufferCapacity )
    {
      m_minimumActivePreFetchSize = minimumActivePreFetchSize;
      m_maximumActivePreFetchSize = maximumActivePreFetchSize;
    }

    public DynamicBufferConfiguration(
      int minimumBufferCapacity,
      int maximumBufferCapacity,
      int minimumActivePreFetchSize,
      int maximumActivePreFetchSize,
      int minimumPassivePreFetchSize,
      int maximumPassivePreFetchSize )
      : this( minimumBufferCapacity, maximumBufferCapacity, minimumActivePreFetchSize, maximumActivePreFetchSize )
    {
      m_minimumPassivePreFetchSize = minimumPassivePreFetchSize;
      m_maximumPassivePreFetchSize = maximumPassivePreFetchSize;
    }

    #endregion

    internal override void Initialize( BufferInfo bufferInfo )
    {
      bufferInfo.SetRequestsHistoryLength( DynamicBufferConfiguration.HistoryLength );

      bufferInfo.SetCapacityRange( m_minimumBufferCapacity, m_maximumBufferCapacity );
      bufferInfo.SetActivePreFetchingSizeRange( m_minimumActivePreFetchSize, m_maximumActivePreFetchSize );
      bufferInfo.SetPassivePreFetchingSizeRange( m_minimumPassivePreFetchSize, m_maximumPassivePreFetchSize );

      bufferInfo.State = new Storage();
    }

    internal override int GetActivePreFetchSize( BufferInfo bufferInfo )
    {
      int fetchSize = DynamicBufferConfiguration.GetStorage( bufferInfo ).ActivePreFetchSize;

      // If the buffer contains a lot of free space, try to boost the active pre-fetch size
      // in order to fill out those spaces quicker.
      int emptySpace = bufferInfo.Capacity - bufferInfo.Size;
      if( emptySpace > fetchSize )
      {
        fetchSize = ( int )Math.Ceiling( fetchSize * DynamicBufferConfiguration.ActivePreFetchSizeBoostRatio );
      }

      return fetchSize;
    }

    internal override int GetPassivePreFetchSize( BufferInfo bufferInfo )
    {
      return DynamicBufferConfiguration.GetMaximumFetchSize( bufferInfo.RequestsHistory );
    }

    internal override int GetBufferCapacity( BufferInfo bufferInfo )
    {
      // Find an estimation of the number of items that is required per second.
      double consumptionRate = DynamicBufferConfiguration.GetConsumptionRate( bufferInfo );
      bool isStagnant = ( consumptionRate <= 0d );

      // Find out the desired time it would take to consume the whole buffer
      // if there was no pre-fetching.
      double spareTimeInSeconds = DynamicBufferConfiguration.GetSpareTimeInSeconds();

      // Find out the maximum fetch size requested by the client.
      int maximumFetchSize = DynamicBufferConfiguration.GetMaximumFetchSize( bufferInfo.RequestsHistory );

      // Find out the number of items we must have to fill out the requests for a given period of time.
      int requiredCapacity = ( isStagnant )
                               ? ( int )Math.Ceiling( maximumFetchSize * spareTimeInSeconds )
                               : ( int )Math.Ceiling( consumptionRate * spareTimeInSeconds );

      // Find out the response time of the data source.
      TimeSpan responseTime = DynamicBufferConfiguration.GetResponseTime( bufferInfo );

      // Find out the active pre-fetch size based on the consumption rate.
      int activePreFetchSize = ( int )Math.Ceiling( consumptionRate * responseTime.TotalSeconds * DynamicBufferConfiguration.ActivePreFetchSizeBoostRatio );

      // Store the active pre-fetch size for further use.
      Storage storage = DynamicBufferConfiguration.GetStorage( bufferInfo );
      storage.MaximumFetchSize = Math.Max( storage.MaximumFetchSize, maximumFetchSize );
      storage.ActivePreFetchSize = ( isStagnant )
                                     ? Math.Max( storage.ActivePreFetchSize, maximumFetchSize )
                                     : activePreFetchSize;

      // Extend the required capacity to create a free space where the pre-fetched items
      // may be placed.
      requiredCapacity += activePreFetchSize;

      // The required capacity doesn't take into account the fact that the buffer has a 
      // center of gravity which may lower the expected capacity.  We must boost the 
      // required capacity here in order to counter the effect of the center of gravity.
      int capacity = DynamicBufferConfiguration.ExtendBufferCapacity( bufferInfo, requiredCapacity );
      capacity = Math.Max( capacity, storage.MaximumFetchSize );

      // Since the client isn't consuming any data right now, keep the
      // buffer as it is except if we think it would be better to enlarge it
      // based on past experience.
      if( isStagnant )
      {
        capacity = Math.Max( capacity, bufferInfo.Capacity );
      }
      // The client is consuming some of the items that are in the buffer.
      // Allow the buffer to shrink if it way too large for the current
      // consumption rate.
      else
      {
        // If the new capacity is lower than the current buffer size, minimize the number of
        // items lost just in case the buffer will increase again next time.
        capacity = DynamicBufferConfiguration.ShrinkBufferCapacity( bufferInfo, capacity );
      }

      return capacity;
    }

    private static Storage GetStorage( BufferInfo bufferInfo )
    {
      Storage storage = bufferInfo.State as Storage;
      Debug.Assert( storage != null );

      return storage;
    }

    private static double GetConsumptionRate( BufferInfo bufferInfo )
    {
      Storage storage = DynamicBufferConfiguration.GetStorage( bufferInfo );

      // Find an estimation of the number of items that is required per second.
      double consumptionRate = DynamicBufferConfiguration.GetItemsConsumedPerSecond( bufferInfo );

      // No items have been requested during a period of time.  Use an old comsumption rate.
      if( consumptionRate <= 0d )
      {
        // We have no idea of the consumption rate.  Take the an old consumption rate instead.
        if( storage.ConsumptionRate.HasValue )
        {
          consumptionRate = storage.ConsumptionRate.Value;
        }
      }
      else
      {
        storage.ConsumptionRate = consumptionRate;
      }

      return consumptionRate;
    }

    private static TimeSpan GetResponseTime( BufferInfo bufferInfo )
    {
      Storage storage = DynamicBufferConfiguration.GetStorage( bufferInfo );

      // Find out the number of items the data source may transfer per second.
      TimeSpan responseTime = DynamicBufferConfiguration.GetResponseTime( bufferInfo.RequestsHistory );

      if( responseTime <= TimeSpan.Zero )
      {
        responseTime = storage.ResponseTime.GetValueOrDefault( TimeSpan.Zero );
      }
      else
      {
        storage.ResponseTime = responseTime;
      }

      return responseTime;
    }

    private static double GetSpareTimeInSeconds()
    {
      double spareTimeInSeconds = DynamicBufferConfiguration.SpareTime.TotalSeconds;

      return Math.Max( spareTimeInSeconds, 0d );
    }

    private static int ExtendBufferCapacity( BufferInfo bufferInfo, int minimumCapacity )
    {
      double centerOfGravity = bufferInfo.CenterOfGravity;
      int capacity;

      if( ( centerOfGravity > 0d ) && ( centerOfGravity < 1d ) )
      {
        double centerOfGravityRatio = Math.Max( centerOfGravity, 1d - centerOfGravity );
        double newCapacity = minimumCapacity / centerOfGravityRatio;

        if( ( !double.IsNaN( newCapacity ) ) && ( !double.IsInfinity( newCapacity ) ) )
        {
          capacity = ( newCapacity > int.MaxValue ) ? int.MaxValue : ( int )Math.Ceiling( newCapacity );
        }
        else
        {
          capacity = minimumCapacity;
        }
      }
      else
      {
        capacity = minimumCapacity;
      }

      return capacity;
    }

    private static int ShrinkBufferCapacity( BufferInfo bufferInfo, int maximumCapacity )
    {
      Storage storage = DynamicBufferConfiguration.GetStorage( bufferInfo );
      int capacity = Math.Max( maximumCapacity, bufferInfo.Capacity );

      // The request capacity is lower than the number of items in the buffer.
      // We'll have to lose some items in order to shrink the buffer.
      if( maximumCapacity < bufferInfo.Size )
      {
        int shrinkDifference = ( int )Math.Floor( bufferInfo.Capacity * DynamicBufferConfiguration.ShrinkThresholdRatio );

        // Prevent the buffer from shrinking since the change is insignificant.
        if( maximumCapacity > bufferInfo.Capacity - shrinkDifference )
        {
          storage.ShrinkCount = 0;
        }
        // The buffer was asked to shrink many times.  Shrink it now even if it means
        // losing items.
        else if( storage.ShrinkCount >= DynamicBufferConfiguration.ShrinkCountToReleaseItems )
        {
          int shrinkSize = ( int )Math.Ceiling( ( bufferInfo.Capacity - maximumCapacity ) * DynamicBufferConfiguration.ShrinkRatio );

          capacity -= shrinkSize;
          storage.ShrinkCount = 0;
        }
        // Do no shrink the buffer yet.  It may grow back again in a few queries.
        // We want to avoid to requery for the same items as most as possible.
        else
        {
          storage.ShrinkCount++;
        }
      }
      else
      {
        storage.ShrinkCount = 0;
      }

      return capacity;
    }

    private static int GetMaximumFetchSize( IEnumerable<BufferRequestInfo> requestsHistory )
    {
      int maximum = 0;

      foreach( BufferRequestInfo request in requestsHistory )
      {
        PassivePreFetchingBufferRequestInfo passiveRequest = request as PassivePreFetchingBufferRequestInfo;

        if( passiveRequest != null )
        {
          maximum = Math.Max( maximum, passiveRequest.FetchSize );
        }
      }

      return maximum;
    }

    private static double GetItemsConsumedPerSecond( BufferInfo bufferInfo )
    {
      DateTime now = DateTime.Now;
      List<BufferRequestInfo> requestsHistory = ( from ri in bufferInfo.RequestsHistory
                                                  where !( ri is ActivePreFetchingBufferRequestInfo )
                                                      && ( now.Subtract( ri.TimeStamp ) <= DynamicBufferConfiguration.SpareTime )
                                                  orderby ri.TimeStamp descending
                                                  select ri ).ToList();
      double consumptionRate = 0d;

      // There is at least a request we can use.
      if( requestsHistory.Count > 0 )
      {
        requestsHistory.ForEach( ( ri ) => consumptionRate += ri.FetchSize );

        // Find out the elapsed time.
        TimeSpan interval = now.Subtract( requestsHistory.Last().TimeStamp );
        // Prevent the consumption rate from exploding if the time interval is too short.
        double intervalInSeconds = Math.Max( 0.1d, interval.TotalSeconds );

        if( ( requestsHistory.Count > 1 ) || ( intervalInSeconds >= 1d ) )
        {
          // Make sure the time interval is big enough to get an appropriate estimation.
          consumptionRate /= Math.Min( intervalInSeconds, requestsHistory.Count );
        }
      }

      return consumptionRate;
    }

    private static TimeSpan GetResponseTime( IEnumerable<BufferRequestInfo> requestsHistory )
    {
      TimeSpan passiveResponseTime = DynamicBufferConfiguration.GetAverageResponseTime( ( from ri in requestsHistory
                                                                                          where ( ri is PassivePreFetchingBufferRequestInfo )
                                                                                          select ri.ResponseTime ) );
      TimeSpan activeResponseTime = DynamicBufferConfiguration.GetAverageResponseTime( ( from ri in requestsHistory
                                                                                         where ( ri is ActivePreFetchingBufferRequestInfo )
                                                                                         select ri.ResponseTime ) );

      if( passiveResponseTime <= TimeSpan.Zero )
      {
        return activeResponseTime;
      }
      else if( activeResponseTime <= TimeSpan.Zero )
      {
        return passiveResponseTime;
      }
      else
      {
        return TimeSpan.FromSeconds( ( activeResponseTime + passiveResponseTime ).TotalSeconds / 2 );
      }
    }

    private static TimeSpan GetAverageResponseTime( IEnumerable<TimeSpan> responseTimes )
    {
      TimeSpan sum = TimeSpan.Zero;
      int count = 0;

      foreach( TimeSpan responseTime in responseTimes )
      {
        sum += responseTime;
        count++;
      }

      if( count <= 1 )
        return sum;

      return TimeSpan.FromMilliseconds( sum.TotalMilliseconds / count );
    }

    #region Private Fields

    private int m_minimumBufferCapacity = DynamicBufferConfiguration.MinimumBufferCapacity;
    private int m_maximumBufferCapacity = DynamicBufferConfiguration.MaximumBufferCapacity;
    private int m_minimumActivePreFetchSize = DynamicBufferConfiguration.MinimumActivePreFetchSize;
    private int m_maximumActivePreFetchSize = DynamicBufferConfiguration.MaximumActivePreFetchSize;
    private int m_minimumPassivePreFetchSize = DynamicBufferConfiguration.MinimumPassivePreFetchSize;
    private int m_maximumPassivePreFetchSize = DynamicBufferConfiguration.MaximumPassivePreFetchSize;

    #endregion

    #region Private Storage Nested Type

    private class Storage
    {
      internal Nullable<double> ConsumptionRate;
      internal Nullable<TimeSpan> ResponseTime;
      internal int ActivePreFetchSize;
      internal int MaximumFetchSize;
      internal int ShrinkCount;
    }

    #endregion
  }
}
